package practice_2025_8_26;

class Solution {
    public int findKthLargest(int[] nums, int k) {
        return find(nums, k, 0, nums.length - 1);
    }
    public int find(int[] nums, int k, int begin, int end) {
        if (begin >= end) {
            return nums[begin];
        }
        int key = nums[(begin + end) / 2];
        System.out.println(key);
        // 通过 left, right, cur将数组分段
        // [begin, left]: < key
        // [left + 1, cur]: = key
        // [cur + 1, right - 1]: 未处理
        // [right, end]: > key
        int left = begin-1, right = end + 1, cur = begin;
        while(cur < right) {
            if(nums[cur] < key) {
                left++;
                //System.out.println("left: " + left + " cur: " + cur);
                swap(nums, left, cur);
                cur++;
            } else if(nums[cur] == key) {
                cur++;
            } else {
                right--;
                swap(nums, right, cur);
            }
            
        }
        //System.out.println("left: " + left + " right:" + right);
        // 判断 k 所处位置
        int a = end - left;
        int b = end - right + 1;
        if (k <= b) {
            return find(nums, k, right, end);
        } else if (k <= a) {
            return key;
        } else {
            return find(nums, k - a, begin, left);
        }
    }
    public void swap(int[] nums, int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
}